<html>
<title>Your Grandmother's guide to Algorithms</title>
<body>
<table width="800" summary="Title">
<tr>
	<td width="70%" align="center"><h1><u>Your Grandmother's guide<br>to Algorithms</u></h1></td>
	<td width="30%" align="center" valign="center">
		<img src="grandmotheinstein.jpg" alt="Valid HTML 4.01 Transitional" ></a>
	</td>
</tr>
</table>

Java and Ruby implementations of several algorithms and computer science related material.<br>
In the future, this will be a full guide to algorithms, which will be so clear
and easy, that even your grandmother will understand it.

<center><h2>News!</h2></center>
Since I've been hired as a [junior] Ruby programmer :-), I'm going to write 
all the implementations both in Ruby and Java (and clean where appropriate).

<center><h2>Contents</h2></center>
<ul>
<li>A basic LL(1) SQL grammar and parser. [4/5, Java].<br>
	Currently being rewritten with JavaCC; previously was written using
	an unmantainable parser generator (Coco/J).</li>
<li>Implementation of main join algorithms [2, Java]:<ul>
	<li>Nested loops</li>
	<li>Sort-Merge</li>
	<li>Hash</li>
	</ul>
<li>Red/Black binary tree [6/7, Java]; note: the deletion algorithm is a
    refactoring of the Sun JDK 6 version.</li>
<li>B+-Tree [2, Java]: in-memory version; the version with page swapping is available as 
	part of the TinyHorrorSQL project</li>
<li>Merge sort [1].</li>
<li>Max/Min heaps [1]</li>
<li>Dijkstra's shortest path [3]</li>
<li>Huffman coding [1, Java]</li>
<li>Rabin-Karp string matching [1]; the hash algorithm used is designed for
	short patterns only.</li>
</ul>

The algorithms are written in both Java and Ruby, except where specified.<br>
<h3>The projects are for the platforms <i>Eclipse 3.3</i> for Java and 
<i>NetBeans 6</i> for Ruby.<br>
Ruby code is not commented, so if you're interested in the Ruby version, you
should download the Java version too.</h3>

<h3>Sources</h3>
<ul>
<li>1. Introduction to algorithms (T.Corben et al.)</li>
<li>2. Fundamentals of database systems (Elmasri/Navathe)</li>
<li>3. Around</li>
<li>5. Compiling with C# and Java (P.Terry)</li>
<li>6. Wikipedia</li>
<li>7. Sun JDK 5/6</li>
</ul>

<center><h2>Design issues</h2></center>
<ol>
<li>The implementations are <b style="font-size:72">intentionally large
and unoptimized</b></font></li>
<li>From an educational standpoint, I have the feeling that procedural 
structuring is more appropriate than object-oriented when dealing with 
algorithms; nonetheless as a programmer I am very strongly OO, so that I find 
it difficult to resist to thinking in objects; also, some solutions are very 
nice if implemented in objects.<br>
A clear example is the Huffman coding, which mixes procedural and OO in the
same place.<br>
My final decision, took <i>after</i> the Huffman coding implementation is to 
write the <i>core</i> of the algorithms procedurally, and any <i>helper</i> 
code in objects. This will sound horrible from an OO perspective, but it's an 
appropriate design for the objective of this project.</li> 
</ol>

<center><h2>Download/License</h2></center>
You can download the code from google code from <a href="http://code.google.com/p/savutils/downloads/list">this link</a>.
or you can directly browse the <a href="http://code.google.com/p/savutils/svn">SVN tree</a>.
<p>
The additional libraries can be downloaded from the same download page, and must 
be added to the 'lib' folder; Coco/J is needed by the parser, and JGraph is 
used as a general tool for tree displaying.<br>
The routines to display the trees are awful, but they just work.
<p>
The code is released under the new BSD license.

<center><h2>Updates/Plans</h2></center>
<ul>
<li>Convert all algos to Ruby and change:</li>
<ul>
	<li>Complete Red/Black binary tree.</li>
	<li>Clean Huffman coding: is there a more simpler/cleverer way for 
		decoding?</li>
</ul>
<li>Convert grammar to JavaCC</li>
<li>Complete Ketchup4J.</li>
</ul>

<b>Latest update (2008/Jan):</b><ul>
<li>Started grammar rewriting with JavaCC</li>
<li>Added Java Red/Black [insertion only]</li>
<li>Added Ruby Dijkstra.</li>
<li>Converted Rabin-Karp and changed hash fx to an appropriate one.</li>
<li>Added very simple rake file for compressing the project to ZIP.</li>
</ul>

<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
var pageTracker = _gat._getTracker("UA-3413058-2");
pageTracker._initData();
pageTracker._trackPageview();
</script>
</body>
</html>